package org.example.myleet.p1601;

public class Solution {

    int maxOperableCount;

    public int maximumRequests(int n, int[][] requests) {
        maxOperableCount = 0;
        int[] in = new int[n];
        int[] out = new int[n];
        dfs(requests, n, 0, in, out);
        return maxOperableCount;
    }

    private void dfs(int[][] requests, int n, int i, int[] in, int[] out) {
        if (i >= requests.length) {
            int count = 0;
            for (int j = 0; j < n; ++j) {
                if (in[j] != out[j]) {
                    return;
                }
                count += in[j];
            }
            maxOperableCount = Math.max(maxOperableCount, count);
            return;
        }
        int[] request = requests[i];
        //不选
        dfs(requests, n, i + 1, in, out);
        //选
        ++in[request[1]];
        ++out[request[0]];
        dfs(requests, n, i + 1, in, out);
        //回溯
        --in[request[1]];
        --out[request[0]];
    }
}
